The present invention relates to a packet switching network, and more particularly a multi-stage interconnection network having several switching stages.
High speed packet switching is a key technology for Broad-band Integrated Services Digital Network (B-ISDN). Currently, Asynchronous Transfer Mode (ATM) is receiving tremendous attention for the next generation of communication technology. The ATM was defined by the CCITT (currently ITU-T) which is the United Nations (U.N) body which defines future telecommunication standards. The basic Protocol Data Unit (PDU) of ATM, which is called a cell, has a fixed length of 53 bytes. ATM switching can be classified as part of the larger category packet switching.
The high speed packet switch is a key technology for B-ISDN technology. There are many requirements for the architecture of a high speed packet switch, such as a modularity and high fault-tolerance, which contribute to easy implementation and good quality of service. Such technology is disclosed in xe2x80x9cATM Technology for Corporate Networksxe2x80x9d, IEEE Communications Magazine, pages 90-101, April, 1992.
A packet switch is a system that is connected to multiple transmission links and does the central processing for the activity of a packet switching network where the network consists of switches, transmission links and terminals. The transmission links are connected to network equipment, such as multiplexers (MUX) and demultiplexers (DMUX). A terminal can be connected to the MUX/DMUX or it can be connected to the packet switch system. Generally, the packet switch consists of input and output transmission link controllers and the switching network. The input and output link controllers perform the protocol termination traffic management and system administration related to transmission jobs and packet transmission. These controllers also process the packets to help assist in the control of the internal switching of the switching network.
The switching network of the packet switch performs space-division switching which switches each packet from its source link to its destination link. There are many known architectures for switching networks. The important characteristics for a switching network are self-routing for high speed switching, short transmission delays, low delay variance, good fault tolerance for high quality service, and high reliability for easy maintenance. Generally, the switching networks are composed of several switching stages with a web of interconnections between adjacent stages. These network are called Multi-stage Interconnection Networks (MIN). Each stage consists of several basic switching elements where the switching elements perform the switching operation on individual packets for self-routing of the packets.
Self-routing enables each packet to be processed by the distributed switching elements without a central control scheme, and thus high speed switching can be done.
The architecture of packet switching networks can be classified by the buffering scheme employed in the network for various queues. For example, input queuing, output queuing, input/output queuing, crosspoint queuing, central queuing, internal queuing and the like.
Input queuing suffers from what is called the xe2x80x9chead of linexe2x80x9d problem (e.g., head of line:HOL). The head of line problem occurs when a packet at the head of line, or first-in position, in a first-in-first-out (FIFO) input buffer is blocked by an output collision with another packet in the network. While the HOL packet is blocked, the other packets in the FIFO buffer are also blocked as they await their turn for the head of line position in the FIFO input buffer while their output destinations are not occupied by other routing requests.
Output queuing is better than input queuing because it does not suffer from the HOL problem, but the buffer size for each output port must be increased as the number of input ports increases. Internal queuing and crosspoint queuing also increase the hardware complexities as the number of ports increases. Central queuing has a bottleneck caused by the speed of memory accesses within the central queue which increases with the number of ports.
Switching networks can also be classified as time division switches in addition to space division. There are many proposed architectures for each division method, as disclosed in xe2x80x9cATM Technology for Corporate Networksxe2x80x9d, IEEE Communications Magazine, pages 90-101, April, 1992.
The time division switching technique is not adequate for large scale switching systems. Under the space division switching technique, a single path network has some problems such as low maximum throughput and hardware complexity. However, the matrix for the time division technique combined with the fully interconnected architecture of space division technique has good performance and can be adapted to the design of the basic elements, as disclosed in xe2x80x9cIntegrated Services Packet Network Using Bus Matrix Switchxe2x80x9d, IEEE Journal on Selected Areas in Communications Magazine, 22(4): 24-31, April, 1994.
Among multiple path switching networks, a recirculating scheme causes an increase in the number of inlets due to the recirculated lines, so that it is not adequate for a large scale switching system. This technology is disclosed in xe2x80x9cSTARLITE: A Wideband Digital Switchxe2x80x9d, GLOBECOM, pages 121-125, November 1984.
On the other hand, tandem banyan networks (discussed in xe2x80x9cArchitecture, Performance, and Implementation of the Tandem Banyan Fast Packet Switchxe2x80x9d, IEEE Journal on Selected Areas in Communications, 9(8):1173-1193, October 1991; U.S. Pat. No. 5,541,914), parallel banyan networks (discussed in xe2x80x9cAnalysis of Out-of-Sequence Problem and Preventative Schemes in Parallel Switch Architecture for High-speed ATM Networkxe2x80x9d, IEEE-Proceeding-Communications, 141(1):29-38, February 1994), load sharing networks (discussed in xe2x80x9cPerformance of Unbuffered Shuffle-exchange Networksxe2x80x9d, IEEE Transactions on Computers, c-35(6): 573-577, June 1986), dilated networks (discussed in xe2x80x9cBroadband Packet Switches Based on Dieted Interconnection Networkxe2x80x9d, IEEE Transactions on Communications, 42(2.3.4): 732-744, 1994) and close networks (discussed in xe2x80x9cA Modular Architecture for Very Large Packet Switchesxe2x80x9d, IEEE Transactions on Communications, 38(7): 1097-1106, 1990) are each good candidates for the architecture of a large scale ATM switching system.
In multiple path switching networks, the number of paths from a given input port to a given output port can be one measure of the performance. A banyan network is a network which has one and only one path from each input port to each output port. A tandem banyan network serially connects each banyan network so that multiple routing trials can be taken. A parallel banyan network is one in which several networks are connected in parallel with one another. A rerouting network is one in which respective banyan networks are overlapped, so that a packet which has failed in one routing trial can restart its routing path at the next stage of the network. Among the different types of networks, the rerouting network has the largest number of routing paths for a given level of hardware complexity.
Lawrie has reported on an omega network for data access and alignment using an array processor in order to access multiple data at the same time in xe2x80x9cAccess and Alignment of Data in an Array Processorxe2x80x9d, IEEE Transactions on Computers, C-24(12):1145-1155, December 1975. The omega network consists of n switching stages (where n=logsN stages with N being the number of input ports and the number of input ports, i.e. the number of input and output ports being the same is a xe2x80x9csquare sizexe2x80x9d network). Each of the n switching stages is composed of N/2 basic switching elements and each switching element performs 2xc3x972 switching.
FIG. 1 shows an embodiment of an omega network having a two port perfect shuffle interconnection scheme. The omega network supports bi-directional routing and the number of perfect shuffle connections is the same as the number of switching stages. But one perfect connection can be omitted if support for single-directional routing can be omitted. Perfect shuffling of N wires is obtained by separating the bottom N/2 wires from the top N/2 wires and precisely interleaving the two blocks with the bottom wires remaining on the bottom, as disclosed in xe2x80x9cPermutation By Cutting and Shufflingxe2x80x9d, SIAM Review, 3(4):293-298, October 1961.
The perfect shuffle connection can also be explained as follows: if we number the switching elements from top to bottom with binary number, such as (bnxe2x88x921bnxe2x88x922, . . . b1), then the upper output port is connected to the next switching stage element with the next highest number (bnxe2x88x922bnxe2x88x923. . . b10) and the lower output port is connected to the next lower switching stage element (bnxe2x88x922bnxe2x88x923 . . . . b11), as discussed in xe2x80x9cOn a Numbered Class of Multistage Interconnection Networksxe2x80x9d, IEEE Transaction on Computers, C-29(8): 694-702, August 1980. For example, the switching element xe2x80x9c10xe2x80x9d of the second stage STG102 in FIG. 1 is connected with the switching element xe2x80x9c00xe2x80x9d in third stage STG103 through the upper output port connection and with the switching element xe2x80x9c01xe2x80x9d in the third stage STG103 through the lower output connection. The omega network is also known to be topologically equivalent to a baseline network, flip network, modified data manipulator (discussed in xe2x80x9cArchitecture, Performance, and Implementation of the Tandem Banyan Fast Switchxe2x80x9d, IEEE Journal on Selected Area in Communication, 9(8):1173-1193, October 1991), indirect binary n-cube network (discussed in xe2x80x9cThe Indirect Binary Ncube Microprocessor Arrayxe2x80x9d, IEEE Transaction on Computers, C26(5):458-473, May 1977), and regular SW banyan network (discussed in xe2x80x9cOn a Class of Multistage Interconnection Networksxe2x80x9d, IEEE Transaction on Computers, C-29(8):694-702, August 1980). The omega network is also a banyan network because it has a unique path from each input port to each output port.
The omega network is self-routing, as is shown in the packet routing example of FIG. 2. The example packet, with a destination address value of xe2x80x9c001xe2x80x9d, starts from the source port,xe2x80x9c011xe2x80x9d, and sequentially passes switching elementsxe2x80x9c01xe2x80x9d, xe2x80x9c10xe2x80x9d and xe2x80x9c00xe2x80x9d of stages STG201, STG202 and STG203, respectively, arriving at its destination port xe2x80x9c001xe2x80x9d. The routing tag of the packet is the destination address where the most significant bit is used for routing at the first stage and the least significant bit is used for routing at the last stage. Note that the relative distance from each intermediate routing switching element to the destination port does not necessarily monotonically decrease with the number of switching stages traversed by the packet. This characteristic is in contrast to the modified data manipulator where each packet monotonically approaches the destination port in terms of physical distance.
For example, the example packet in FIG. 2 is one row apart from the corresponding switching element of the destination port at first stage STG201, but the packet diverges further away from the destination port at second stage STG202. But the example packet does make its way towards the destination port at each stage. The distance traveled by the packet is not so much the physical distance to the destination but manifests itself as the length of the connection wires through which the packet passes. The number of interconnection wires is numbered from top to bottom as (bnxe2x88x921, bnxe2x88x922, . . . b0). The approach can be observed by connection wires of the routing path, 010xe2x86x92100xe2x86x92001, as shown in FIG. 2. The number of underlined bits increases as the number of stages traversed increases and the address of the interconnection wire eventually becomes the same as the destination address when the example packet has passed through all n routing stages.
With rapid growth in semiconductor processing technology, almost all electronic systems use VLSI (Very Large Scale Integrated) chips. The reasons for VLSI are rapid response speed, low cost, small space usage and feasibility. The size of a packet switch for the public network is very large, as discussed in xe2x80x9cATM Concepts, Architecture, and Protocolsxe2x80x9d, Communications of the ACM, 38(2):30-38, 109, February 1995.
To implement a large scale system, the use of VLSI is inevitable and sufficient care should therefore be taken to design a network architecture that is amenable to VLSI implementation. At an early stage of the design process for a network architecture, the designer should consider which basic VLSI chips will constitute the network so that the logic can be easily partitioned for each VLSI chip. In other words, a good architecture that is adequate for VLSI is necessary.
The requirements of a good architecture for VLSI is low hardware complexity and modularity of the architecture for easy functional partitioning for a chip. The number of different types of chips should be minimized for low cost and easy maintenance. In terms of system implementation, the number of chips and the number of different types of chips greatly affects the system cost. The number of chips is highly dependent on the total hardware complexity of the switch architecture and the number of chip types is dependent on the modularity of the architecture.
With the development of VLSI technology, the amount of functional logic that can be partitioned into a single chip is now limited by the interface pin count of the functional block rather than the number of logic gates within the functional block. The number of logic gates that can be placed on a single chip has greatly increased due to the rapid evolution in processing technology, but the pin count for a chip is still mechanically limited. There is technology, such as multi-chip module (MCM) or wafer scale integration (WSI), which makes the complex connections inside a module or on a wafer. But the total pin count in these technologies still does not typically exceed 500. For example, the well known Pentium Pro microprocessor produced by Intel Corporation is an MCM device that has about 5.5 million transistors but has an interface pin count of 387.
A switching network, however, is a difficult architecture to implement using chips because it has so many interconnection wires that the number of interface pins that are required when it is partitioned into chips becomes unmanageable. Nevertheless, it is extremely important for the switching network to have the high performance of VLSI devices in order to obtain high speed switching.
FIG. 3 demonstrates the difficulty in functionally partitioning a switching network for implementation on using a single type of chip. When a functional partition is made for any one of subsystems M1, M2, or M3, the resulting 8xc3x978 switch cannot be made using a single type of chip because the associated interconnection scheme between switch elements inside the chip is fixed and cannot be changed once the chip is fabricated to accommodate a particular specialized design not previously considered.
When subsystem M4 is selected for the functional partition, then only one type of chip is sufficient to implement the 8xc3x978 switch because the interconnection wires among switching elements are external to the chip and can be changed to accommodate the specialized design. Even though the modularity in FIG. 3 was explained as if the modularity can be obtained simply through the selection of a functional partitioning method, in reality, the modularity of the network design is highly dependent on the interconnection scheme of the multi-stage interconnection network.
Good fault tolerance is also very important for any system but it is essential for large scale packet switches because they are typically used as part of the public switching network. Modular architecture is important for good fault tolerance as well as easy functional partitioning. FIG. 4 illustrates the inefficiency of fault recovery in a modified data manipulator. If there is a faulty element in the system, as shown by the shaded switch element in FIG. 4, then the faulty element should be removed from the system to prevent system performance degradation and maintain high quality service. If the element is not replaceable because it is integrated into a chip, then the entire chip module, which is the basic modular block in the system, must be replaced. If a banyan network is the smallest modular block then the banyan network chip with the faulty element must be replaced. However, the faulty element replacement must be performed on-line without a system shutdown in order to maintain continuous service to users of the network. To replace a chip module, a manual operation is required along with a system shutdown in order to protect the new module from a power shock and to maximize the system stability.
It is, therefore, an object of the present invention to provide a multistage interconnection network having a high degree of integration.
It is another object of the present invention to provide a multi-stage interconnection network having a highly fault-tolerant architecture.
It is a further object of the present invention to provide a packet switch system having modular characteristics, so that functional division for a single chip design can be easily achieved.
It is an additional object of the present invention to provide a packet-switched self-routing multistage interconnection network having a low packet loss rate. According to one embodiment of the present invention, a multi-stage (NXN) interconnection network having N input ports and N output ports, for transmitting packets from the input ports to the output ports, comprises a multi-stage packet switching network having at least logMN switching stages, each of the switching stages having N/2 MXM switching elements where M is the number of input or output ports of each switching element. Each switching element of each stage comprises X bypassing input ports, Mxe2x88x92X input routing ports, X bypassing output ports and Mxe2x88x92X output routing ports, where X is an integer greater than 0. The bypassing output port of each switching element is connected to the bypassing input ports of a corresponding switching element in a next stage, respectively, and the output routing ports of each switching element at each stage are connected to the input routing ports of each of the switching elements of the next stage by means of a perfect shuffle connection scheme.
According to another embodiment of the present invention, a packet switch system includes an input module for receiving an original packet from a terminal and converting the original packet into a switching packet by adding an information field related to routing to the original packet, a multi-stage packet switching network for performing the routing of the switching packet, said network having at least logMN switching stages. Each switching stage has N/2 (MXM) switching elements, where M is the number of input or output ports of each switching element. Logic circuitry generates a minimal routing number related to each switching stage and supplies the minimal routing number to the switching elements of each stage. An output module receives the switching packet from the multi-stage packet switching network and converts the switching packet into the original packet by removing the information field from the switching packet. Each switching element at each stage comprises X bypassing input ports, Mxe2x88x92X input routing ports, X bypassing output ports and Mxe2x88x92X output routing ports, where X is an integer greater than 0. The bypassing output ports of each switching element at each stage are connected to the bypassing input ports of each of the switching elements which are disposed in a corresponding position of a next stage. The output routing ports of each switching element at each stage are connected to input routing ports of the switching elements at the next stage by means of a perfect shuffle connection scheme. The input routing ports of each switching element at a first stage are connected to the input module.
An embodiment of a method, according to the present invention, for switching packets in a NXN multi-stage inter-connection network, involves providing a plurality of MXM switching elements, where each switching element has M routing input ports, M routing output ports, a bypass input port and a bypass output port and organizing the plurality of MXM switching elements into logMN stages. The method then involves connecting each of the routing input ports of the switching elements in a first stage of the logMN stages to one of the N input ports of the NXN network and connecting each of the routing output ports of the switching elements in a last stage of the logMN stages to one of the N input ports of the NXN network. Finally, the method calls for interconnecting the logMN stages through a perfect shuffle interconnection scheme of the routing input ports and routing output ports of the switching elements in adjacent stages, and interconnecting the bypass output port of each switching element to the bypass input port of a corresponding switching element in the adjacent stage.